Lately, along with the general tendency toward larger capacity recording media such as optical disks, increased data reading speeds have been in demand. Particularly, the reduction of processing time in error correction processors that require a long processing time has been in demand. Therefore, for a reduction in the processing time, the processing speed in the circuits used in the error correction processor should be increased.
In conventional optical disk apparatuses, the error rate of the recording medium (optical disk) is extremely high and a powerful error correction code (ECC) is required. Therefore, a Reed Solomon code has been used as the error correction code ECC for the optical disk. The Reed Solomon code is a byte correction code that treats one byte as an element of a coded word and determines which byte failed and how it did.
Conventionally, a coding system for coding a lot of data with the Reed Solomon codes for the optical disk has been used in combination with an interleave method.
The following describes an example of the structure of arrays of recorded data in the optical disk, referring to FIGS. 8 and 9. As shown in FIG. 8(A), the optical disk 80 is provided with a spiral track 81, one track 82 corresponding to one specified circumferential portion of the spiral track is defined as a single information segment, one track 82 comprises a plurality of sectors 83 as shown in FIG. 8(B), and each sector 83 comprises an ID part and a data part 85 as shown in FIG. 8(C).
In addition, as shown in FIG. 8(D) the data part 85 comprises a user data part 86, a control word part 87, a CRC part 88 and an ECC part 89.
The detailed structure of the data part 85 comprises, as shown in FIG. 8(E), data of 1,024 bytes (DATA 1.about.DATA 1024), a control data word (CW1.about.CW12) of 12 bytes, CRC data of 4 bytes (CRC1.about.CRC4) and ECC data (ECC1.about.ECC160) of 160 bytes in the order of data transfer.
Data corresponding to each sector as described above is actually arranged as shown in FIG. 9 and the code length shown in FIG. 11 is formed with ten coded words, each of which comprises 120 bytes. A line of the array (one coded word) is called one interleave and error correction is carried out for each interleave. Each of interleaves 0.about.9 comprises the error correction code (ECC part) and an information symbol (data part). In FIG. 9, low order 16 bytes, that is, position 0.about. position 15 form the ECC part. In the interleave, the number of information symbols (the length of the data part) is formed with high order 104 bytes (position 16.about. position 119) except the ECC part. The Reed-Solomon code with an extremely high correction ability is used as the error correction code for each interleave.
Though information symbols (data part) corresponding to one sector of the array are 104 bytes.times.10=1040 bytes as shown in FIG. 9, the information symbols are formed with 1036 bytes since the CRC (Cyclic Redundancy Check) code is contained in position 16 of interleaves 6.about.9. The CRC code is included in the data array and is not used for error correction but is used for verifying the result of error correction based on the ECC.
In other words, for reading the data as much as one sector on the optical disk, error correction is carried out for each of interleaves 0.about.9. Then, whether error correction has been properly carried out, is determined based on the data obtained by removing the inspection symbol (ECC part) from the data for which error correction has been finished.
The Reed-Solomon code with an extremely high correction ability is used as the error correction code ECC formed in the interleaves 0.about.9, and 8 bits of data, that is, 1 byte is treated as an element of the coded word, and which byte of one interleave and how it is faulty is determined. This Reed Solomon code of the optical disk uses the elements of the coded word as an element of the Galois finite field GF (2.sup.r) for byte correction.
The following briefly describes the Galois finite field (2.sup.r). The Galois field is a set of numbers having the laws of calculations and, if r=8, the number of elements of the Galois field is 256 (=2.sup.8).
The elements are denoted as shown below: EQU 0, .alpha..sup.0, .alpha..sup.1, .alpha..sup.2, .alpha..sup.3, . . . .alpha..sup.252, .alpha..sup.253, .alpha..sup.254, .alpha..sup.255
Provided, .alpha..sup.0 =.alpha..sup.255 =1 is given and the values of elements are expressed as the numerical values within the range of 1.ltoreq..alpha..sup.n .ltoreq.255.
The Galois field is such that all four rules of calculations including multiplication and division are completed; for example, .alpha..sup.3 .multidot..alpha..sup.3 =.alpha..sup.6 and .alpha..sup.250 .multidot..alpha..sup.10 =.alpha..sup.260 =.alpha..sup.5 .multidot.5 of .alpha..sup.5 is a remainder when 260 is divided by 255. Addition and subtraction can be carried out with Exclusive OR (EOR) in the vector form.
In the case of error correction using this Galois field GF (2.sup.r), one-byte data is treated as an element of the Galois field (2.sup.r), and which element (which one-byte data) and how it is faulty is determined. If the data in which .alpha..sup.2 should be entered is accidentally given, for example, .alpha..sup.5, .alpha..sup.2 +.alpha..sup.x =.alpha..sup.5 is given and this .alpha..sup.x is a faulty numerical value. The code length of the above described Reed-Solomon code using this Galois field has the relation of 2.sup.r -1 and is 2.sup.8 -1=255 bytes at r=8 as shown in FIG. 10. In FIG. 10, the Reed-Solomon code comprises an inspection symbol (ECC part) and an information symbol (data part). The number of inspection symbols (the length of the ECC part) is determined by a generator polynomial of ECC. In this case, the generator polynomial consists of 16 bytes and, in the drawing, low order 16 bytes, that is, position 0.about. position 15, form the ECC part. The number of information symbols (the length of the data part) is high order 239 bytes (position 16.about. position 254) except for the ECC part. The error correction ability of the ECC is determined according to the generator polynomial and, in this case, the correction ability detects and corrects an error of 8 bytes, that is, up to 8 bytes of 255 bytes.
The procedure for error correction is as described below. First, a syndrome is obtained from all data that have been read. This syndrome is a pattern that shows the details of errors of read data, that is, a position of data where the errors take place and the quantity and/or the pattern of numerical values of the errors at that position. A pattern of error corresponds to the syndrome as 1 vs 1 and, if there are no errors, the syndrome is zero. Then, an error locator polynomial and a error evaluator polynomial are obtained from this syndrome. The Euclidean algorithm is generally used for this purpose. Subsequently, the error positions and erroneous numerical values are obtained based on the error locator polynomial and the error evaluator polynomial obtained above. The method for obtaining the error position and erroneous value, using the error locator polynomial and error evaluator polynomial is executed using the chain search method using the chain algorithm.
How to obtain the syndrome is described later.
The chain search method is first described.
The error locator polynomial .sigma.(x) and the error evaluator polynomial .omega. (x) obtained using the Euclidean algorithm are expressed as below. EQU .sigma.(x)=.sigma..sub.0 +.sigma..sub.1 x+.sigma..sub.2 x.sup.2 +. . . +.sigma..sub.n x.sup.n EQU .omega.(x)=.omega..sub.0 +.omega..sub.1 x+.omega..sub.2 x.sup.2 +. . .+.omega..sub.n-1 x.sup.n-1
Coefficients .sigma..sub.0, .sigma..sub.1, . . . .sigma..sub.n, .omega..sub.0, .omega..sub.1, . . . .omega..sub.n-1 are known values obtained by the Euclidean algorithm and expressed with the elements of the Galois fields. n denotes the correction ability and n=8 is obtained since the correction cover 8 bytes as described above. Therefore, the above polynomials are as shown below: EQU .sigma.(x)=.sigma..sub.0 +.sigma..sub.1 x+.sigma..sub.2 x.sup.2 + . . . +.sigma..sub.7 x.sup.7 +.sigma..sub.8 x.sup.8 EQU .omega.(x)=.omega..sub.0 +.omega..sub.1 x+.omega..sub.2 x.sup.2 + . . . +.omega..sub.7 x.sup.7 +.omega..sub.8 x.sup.8
It is known that, in the error locator polynomial .sigma. (x), the solution of .sigma. (x)=0 indicates the error position. When the data at position j1 in position 0 to position 254 in FIG. 10 is faulty, .sigma. (.alpha..sup.-j1)=0 is given. Accordingly, it is known that, for obtaining the solution of .sigma. (x)=0, error position j1 can be obtained by substituting 255 elements of the Galois fields expressed as x=.alpha..sup.0, .alpha..sup.1, .alpha..sup.2 . . . .alpha..sup.254 into the error locator polynomial .alpha. (x) in sequence and obtaining the element that determines .sigma. (x)=0 (chain search).
It is known that the error value e.sub.j1 at that time is obtained from the formula given below. EQU e.sub.j1 =.alpha..sup.-j1.119 .multidot..omega.(.alpha..sup.-j1)/.sigma.'(.alpha..sup.-j1)
.sigma.' (x) is a formal differential of .sigma. (x); for example, if the following is given, EQU .sigma.(x)=.sigma..sub.0 +.sigma..sub.1 x+.sigma..sub.2 x.sup.2 +.sigma..sub.3 x.sup.3 +.sigma..sub.4 x.sup.4 +.sigma..sub.5 x.sup.5, EQU .sigma.'(x)=.sigma..sub.1 .sigma..sub.3 x.sup.2 +.sigma..sub.5 x.sup.4 PA1 (where, Si=A (.alpha..sup.120+i), i=0, 1, . . . 15) EQU A(x)=A.sub.119 X.sup.119 +A.sub.118 X.sup.118 + . . . A.sub.2 X.sup.2 +A.sub.1 X+A.sub.0
is obtained.
The applicant of the present invention has embodied the circuit to obtain the solution of this error locator polynomial .sigma. (x) with the circuit previously shown in the drawing. In FIG. 13, the circuit of the error locator polynomial .sigma. (x) comprises eight multiplication circuits 11.about.18, nine flip-flop circuits (hereafter, simply referred to as "FF") 20.about.28 and an Exclusive OR circuit (hereafter referred to as "EOR circuit") 30. Nine FFs 20.about.28 are 8-bit FFs into which initial values are respectively entered. For initializing FFs 20.about.28 (.sigma..sub.0, .sigma..sub.1 .about..sigma..sub.8), the initializing route shown with a broken line is selected by the selector and FFs 20.about.28 are connected as shift registers.
When the initial inputs are set byte by byte in the order of .sigma..sub.8 .about..sigma..sub.4, the input data are shifted finally up to FF28. Corresponding initial values (coefficients) are set in FFs 20.about.28, respectively. The initializing route simply serves as a shift register and the data (coefficients) initially set are shifted in sequence to an FF toward FF28 each time one byte is set. After the initial values (coefficients) have been set in FFs 20.about.28, nothing is set in this initializing route.
Eight multiplication circuits 11.about.18 respectively have a multiplier value consisting of the Galois field and the multiplier value of the multiplication circuit 11 connected through the operating route shown with a solid line 21 to the FF of coefficient .sigma..sub.1 (hereafter referred to as ".sigma..sub.1 FF"; other FFs to be similarly referred) is .alpha.. Similarly, the multiplier value of the multiplication circuit 12 of the .sigma..sub.2 FF22 is .alpha..sup.2 ; the multiplier value of the multiplication circuit 13 of the .sigma..sub.3 FF23 is .alpha..sup.3 ; the multiplier value of the multiplication circuit 14 of the .sigma..sub.4 FF24 is .alpha..sup.4 ; the multiplier value of the multiplication circuit 15 of the .sigma..sub.5 FF25 is .alpha..sup.5 ; the multiplier value of the multiplication circuit 16 of the .sigma..sub.6 FF26 is .alpha..sup.6 ; the multiplier value of the multiplication circuit 17 of the .sigma..sub.7 FF27 is .alpha..sup.7 and the multiplier value of the multiplication circuit 18 of the .sigma..sub.8 FF28 is .alpha.. Operation is executed in the operation routes based on the clock signals. For example, in the .sigma..sub.8 FF28 and the multiplication circuit (hereafter referred to as ".sigma..sub.8 multiplication circuit"; other multiplication circuits to be similarly referred) 18, the value of the .sigma..sub.8 FF28 after 1 clock is .sigma..sub.8 .multidot..alpha..sup.8, the value after 2 clock is .sigma..sub.8 .multidot..alpha..sup.8 .multidot..alpha..sup.8 =.sigma..sub.8 .multidot..alpha..sup.16 and the value after t clocks is .sigma..sub.8 .multidot.(.alpha..sup.t).sup.8.
Similarly, the operation is carried out in other operation routes. In this connection, the values of other FFs 21.about.27 after t clocks, are .sigma..sub.1 (.alpha..sup.t).sup.1 for .sigma..sub.1 FF21, .sigma..sub.2 (.alpha..sup.t).sup.2 for .sigma..sub.2 FF22, .sigma..sub.3 (.alpha..sup.t).sup.3 for .sigma..sub.3 FF23, .sigma..sub.4 (.alpha..sup.t).sup.4 for .sigma..sub.4 FF24, .sigma..sub.5 (.alpha..sup.t).sup.5 for .sigma..sub.5 FF25,.sigma..sub.6 (.alpha..sup.t).sup.6 for .sigma..sub.6 FF26 and .sigma..sub.7 (.alpha..sup.t).sup.7 for .sigma..sub.7 FF27.
The values of FFs 21.about.28 are the values obtained by substituting .alpha..sup.t for x of the error locator polynomial given below EQU .sigma.(x)=.sigma..sub.0 +.sigma..sub.1 x+.sigma..sub.2 x.sup.2 + . . . +.sigma..sub.7 x.sup.7 +.sigma..sub.8 x.sup.8
that is, the values of the terms given below EQU .sigma.(.alpha..sup.t)=.sigma..sub.0 +.sigma..sub.1 (.alpha..sup.t).sup.1 +.sigma..sub.2 (.alpha..sup.t).sup.2 + . . . +.sigma..sub.8 (.alpha..sup.t).sup.8
The values when .alpha..sup.t is substituted in the error locator polynomial .sigma. (x) can be obtained by adding the values of the terms (values of FFs 20.about.28) at that time, at the EOR circuit 30.
Accordingly, the value of variable x of the error position polynomial .sigma. (x) is substituted and calculated upon each clock in the order of x=.alpha..sup.1, .alpha..sup.2, .alpha..sup.3, . . . .alpha..sup.252, .alpha..sup.253, .alpha..sup.254, .alpha..sup.255. The error position j1 is obtained according to t when the solutions of the error locator polynomial obtained in sequence are 0, that is, the EOR circuit 30 is 0.
When .sigma. (.alpha..sup.t)=0 is given, .alpha..sup.t =.alpha..sup.255-j1, therefore t=255-j1 and accordingly the error position is j1=255-t. For example, when t=236, j1=255-236=19 is given and this indicates that the data of position 19 is faulty in FIG. 10. In other words, an error position is inspected in sequence from the highest position 254 to the lowest position 0 by carrying out operations in sequence from .sigma. (.alpha..sup.1) to .sigma. (.alpha..sup.255) with the clocks (forward search).
Similarly, the erroneous numerical value circuit based on the error evaluator polynomial .omega. (x) basically has the same circuit construction.
FIG. 14 shows the circuit of the numerator part of the above described erroneous numerical value e.sub.j1 =.alpha..sup.-j1.multidot.119 .multidot..omega.(.alpha..sup.-j1)/.sigma.'(.alpha..sup.-j1), which comprises eight multiplication circuits 31.about.38, eight FFs 40.about.47 and the exclusive OR circuit (hereafter referred to as "EOR circuit") 50. Initial setting values (coefficients .omega..sub.0 .about..omega..sub.7) are entered into FFs 40.about.47, respectively. Multiplier values of multiplication circuits 31.about.38 are .alpha..sup.119, .alpha..sup.120 .about..alpha..sup.125 and .alpha..sup.126.
A calculation is repeated with each clock signal and the output of the EOR circuit 50 after t clock signals becomes a value of the numerator of erroneous numerical value e.sub.j1 as shown below EQU .omega..sub.0 (.alpha..sup.t).sup.119 +.omega..sub.1 (.alpha..sup.t).sup.120 + . . . +.omega..sub.7 (.alpha..sup.t).sup.126 =(.alpha..sup.t).sup.119 .omega.(.alpha..sup.t)
Accordingly, the value of variable x is substituted at each time of the clock signal in the order of x=.alpha..sup.1, .alpha..sup.2, .alpha..sup.3, . . . .alpha..sup.252, .alpha..sup.253, .alpha..sup.254, .alpha..sup.255 and the numerator value of the erroneous numerical value ej1 is obtained from the EOR circuit 50.
The following describes a syndrome forming method.
Assuming that the data string of 120 bytes shown in FIG. 12 is the polynomial A (x) and the generator polynomial G (x) of the ECC is EQU G(x)=(X-.alpha..sup.120)(X-.alpha..sup.121) . . . (X-.alpha..sup.134) (X-.alpha..sup.135)
and
the syndrome polynomial S(x) of the data string polynomial A(x) at this time is expressed as a polynomial that has values obtained by substituting .alpha..sup.120, .alpha..sup.121, . . . , .alpha..sup.135 into the polynomial A(x) as the coefficients.
Specifically, when EQU S(x)=S.sub.15 x.sup.15 +S.sub.14 X.sup.14 + . . . +S.sub.1 X+S.sub.0
is given, EQU SO=A(.alpha..sup.120)=A.sub.119 .alpha..sup.120*119 +A.sub.118 .alpha..sup.120*118 + . . . +A.sub.2 .alpha..sup.120*2 +A.sub.1 .alpha..sup.120 A.sub.0
is obtained.
FIG. 15 shows the syndrome generating circuit for the above ECC that comprises 16 flip-flop circuits (hereafter referred to as "FF") 210.about.225 and 16 multiplication circuits 230.about.245 having the EOR matrix for multiplying input values by .alpha..sup.i. 16 FFs 210.about.225 are 8-bit FFs and the initial values are 0.
On the other hand, 16 multiplication circuits 230.about.245 have the multiplier values respectively consisting of the Galois fields. The multiplier value of multiplication circuit 230 connected to FF210 through the operation route is .alpha..sup.120, the multiplier value of multiplication circuit 231 connected to FF211 through the operation route is .alpha..sup.121, the multiplier value of multiplication circuit 232 connected to FF212 through the operation route is .alpha..sup.122, the multiplier value of multiplication circuit 233 connected to FF213 is .alpha..sup.123, and similarly the multiplier values of multiplication circuits 234.about.245 corresponding to .alpha..sup.124 .about..alpha..sup.135 are set in advance.
Under these conditions, values A.sub.119, A.sub.118, A.sub.117, . . . , A.sub.2, A.sub.1 and A.sub.0 at positions 119.about.0 of data of 120 bytes shown in FIG. 12 are entered into 16 operation routes comprising FFs and multiplication circuits in sequence starting from the value of the high order position, that is, A.sub.119.
In the operation route that comprises, for example, FF210 and the multiplication circuit 230 providing multiplier value .alpha..sup.120, the output at the time of the first clock signal A.sub.119. Subsequently, at the second clock signal,
A.sub.119 .alpha..sup.120 +A.sub.118 (+ denotes the exclusive OR as in the following expressions)
at the third clock signal, EQU A.sub.119 (.alpha..sup.120).sup.2 +A.sub.118 .alpha..sup.120 +A.sub.117
and at the 120th clock signal, EQU A.sub.119 .alpha..sup.120*119 +A.sub.118 .alpha..sup.120*118 + . . . +A.sub.2 .alpha..sup.120*2 +A.sub.1 .alpha..sup.120 +A.sub.0
In other words, the above means that, in the operation route that comprises FF210 and the multiplication circuit 230 providing multiplier value .alpha..sup.121, SO=A(.alpha..sup.120) is obtained.
Similarly, in the operation route that comprises FF211 and the multiplication circuit 231 providing multiplier value .alpha..sup.121, the output at the 120th clock signal is as shown below, EQU A.sub.119 .alpha..sup.121*119 +A.sub.118 .alpha..sup.121*118 + . . . +A.sub.2 .alpha..sup.121*2 A.sub.1 .alpha..sup.121 +A.sub.0
and this means that S1=A(.alpha..sup.121) is obtained.
Incidentally, in the operation route that comprises FF225 and the multiplication circuit 245 providing multiplier value .alpha..sup.135, the output at the 120th clock signal is as shown below, EQU A.sub.119 .alpha..sup.135*119 +A.sub.118 .alpha..sup.135*118 + . . . +A.sub.2 .alpha..sup.135*2 +A.sub.1 .alpha..sup.135 +A.sub.0
and this means that S15=A(.alpha..sup.135) is obtained.
Specifically, coefficients A (.alpha..sup.i) (i=120, 122, . . . , 135) of the syndrome polynomial are generated at the timing of the 120th clock signal from 16 operation routes each comprising an FF and a multiplication circuit.
As described above, the error locator polynomial and the error evaluator polynomial are obtained based on the syndromes of the above polynomials A (x), and which byte (position) and how it is faulty can be known according to the error locator polynomial and the error evaluator polynomial. The chain algorithm is used as a method for obtaining the error position by using the error locator polynomial and the error evaluator polynomial (chain search). In addition, the applicant of the present invention has proposed a circuit for simultaneously generating the CRC syndrome in the chain search, which speeds up the error correction processing. (Refer to Patent Application 1991-34790.)
The prior art related to the present invention described above is described in detail in "Essentials of Error Correction Coding Technology" the electronics essentials series No. 20 published by Japan Industrial Technology Center (published on Mar. 20, 1986). It is recommended to refer to the descriptions of this reference literature.
Similarly in an optical disk in which the code length of one interleave is 120 bytes and the number of information symbols is 120 bytes as shown in FIG. 11, the same operations are carried out in the circuit as shown in FIG. 13.
However, the data of the optical disk is processed in 255 bytes as shown in FIG. 10 and therefore the error position is inspected (forward chain search) in sequence from the highest position 254 to the lowest position 0 by supplying clock signals in the circuit of the error locator polynomial .sigma. (x) and carrying out calculations in sequence from .sigma. (.alpha..sup.0) to .sigma. (.alpha..sup.255) and the processing time is wasted. In other words, in the case of the code length of 120 bytes smaller than 255 bytes, error correction processing is executed including effective data from position 119 to position 0 after "0" has been entered into high order positions 254 to 120 and unnecessary processing with unnecessary data has been carried out, and therefore the circuit of the error locator polynomial .sigma. (x) from position 254 to position 120 carries out wasteful processing (chain search). This is the same with the circuit for processing erroneous numerical values shown in FIG. 14.